// https://leetcode.cn/problems/merge-k-sorted-lists/

// 算法思路总结：
// 1. 使用小根堆合并K个有序链表
// 2. 将每个链表的头节点加入最小堆
// 3. 每次取出堆顶最小节点，将其后继节点入堆
// 4. 按顺序连接所有节点形成合并后的链表
// 5. 时间复杂度：O(nlogk)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include "LinkedListUtils.h"

// 优先级队列默认是最大堆，我们要求的是最小堆
struct Compare
{
    bool operator()(const ListNode* l1, const ListNode* l2)
    {
        return l1->val > l2->val;
    }
};

class Solution 
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 1.建立小堆并放入初始数据
        priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;
        for (auto& list : lists)
        {
            if (list)
                minHeap.push(list);
        }

        // 2.一直出堆入堆直到为空
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while (!minHeap.empty())
        {
            auto top = minHeap.top();
            minHeap.pop();

            if (top->next)
                minHeap.push(top->next);

            cur->next = top;
            cur = top;
        }

        return dummy->next;
    }
};

int main()
{
    vector<int> v1 = {1, 4, 5};
    vector<int> v2 = {1, 3, 4};
    vector<int> v3 = {2, 6};
    
    auto l1 = createLinkedList(v1), l2 = createLinkedList(v2), l3 = createLinkedList(v3);
    vector<ListNode*> lists = {l1, l2, l3};

    Solution sol;
    auto l = sol.mergeKLists(lists);
    printLinkedList(l);

    return 0;
}